package Alogorithm;

import java.util.Random;

public class Quitsort {
	 public static void Sort(int array[]){

	        
	        int start = 0;
	        int end = array.length-1;
	        sort(array,start,end);
	        
	        System.out.println("排序后的数组为：");
	        for(int i = 0; i<array.length; i++){
	             System.out.print(array[i]+" ");
	         }
	        System.out.println();
	        
	     }
	     
	     public static void sort(int[] a,int low,int high){
	         int start = low;
	         int end = high;
	         int key = a[low];//数组最开始的值
	         
	         
	         while(end>start){
	             //从后往前比
	             while(end>start&&a[end]>=key)  //如果没有比关键值小的，比较下一个，直到有比关键值小的交换位置，然后又从前往后比�?
	                 end--; 
	             a[start] = a[end];
	             for(int i = 0; i<a.length; i++){
		             System.out.print(a[i]+" ");
		         }
		        System.out.println();
	             //从前往后比
	             while(end>start&&a[start]<=key)//如果没有比关键值大的，比较下一个，直到有比关键值大的交换位�?
	                start++;
	             a[end] = a[start];
	             for(int i = 0; i<a.length; i++){
		             System.out.print(a[i]+" ");
		         }
		        System.out.println();
	         //此时第一次循环比较结束，关键值的位置已经确定了左边的值都比关键小，右边的值都比关键大，但是两边的顺序还有可能是不一样的，进行下面的递归调用
	         }
	         a[start]=key;
	         //递归
	         if(start>low) sort(a,low,start-1);//左边序列。第low个索引位置到关键值索star-1
	         if(end<high) sort(a,end+1,high);//右边序列。从关键值索low+1到最后一high?
	       
	     }
	     public static int partition(int[] a,int low,int high){
			
	    	 int start = low;
	         int end = high;
	         int key = a[low];//数组最开始的值
	         
	         while(end>start){
	             //从后往前比
	             while(end>start&&a[end]>=key)  //如果没有比关键值小的，比较下一个，直到有比关键值小的交换位置，然后又从前往后比�?
	                 end--; 
	             a[start] = a[end];
	             //从前往后比
	             while(end>start&&a[start]<=key)//如果没有比关键值大的，比较下一个，直到有比关键值大的交换位�?
	                start++;
	             a[end] = a[start];
	         //此时第一次循环比较结束，关键值的位置已经确定了左边的值都比关键小，右边的值都比关键大，但是两边的顺序还有可能是不一样的，进行下面的递归调用
	         }
	         a[start]=key;
	    	 return start;
	     }
	     public static void sort1(int[] a,int low,int high){
	         
	         
	         while (low<high) {
	        	 int index=partition(a, low, high);
	        	 sort1(a, low, index-1);
	        	 low=index+1;
			}
	       
	     }
	     

}
